package hl.leco.colle.tree;

import java.util.*;

/**
 * 
 * @author Liu Huan
 */

public class TreeNode {
	
	// 定义二叉树的基本结构
	public int val;
	public TreeNode left;
    public TreeNode right;
    
    // 初始化 节点
	public TreeNode(int val) {
		this.val = val;
	}
	
	// 初始化一个具体的二叉树
	public static TreeNode creatBinaryTree(){
		int[] arr = {1, 2, 3, 4, 5, 6};
		TreeNode root = new TreeNode(arr[0]);
		TreeNode child1 = new TreeNode(arr[1]);
		TreeNode child2 = new TreeNode(arr[2]);
		TreeNode child3 = new TreeNode(arr[3]);
		TreeNode child4 = new TreeNode(arr[4]);
		TreeNode child5 = new TreeNode(arr[5]);
		root.left = child1;
		child1.left = child2;
		child1.right = child3;
		child3.left = child4;
		child3.right = child5;
		return root;
	}
	
	// 前序遍历 递归
	public static void preOrderWithRecursion(TreeNode root){
		if (root!=null){
			System.out.print(root.val);// 访问当前节点数据
			preOrderWithRecursion(root.left);// 递归遍历左子树
			preOrderWithRecursion(root.right);// 递归遍历右子树
		} else {
			return;
		}
	}
	
	// 中序遍历 递归
	public static void inOrderWithRecursion(TreeNode root){
		if (root!=null){
			inOrderWithRecursion(root.left);// 递归遍历左子树
			System.out.print(root.val);// 访问当前节点数据
			inOrderWithRecursion(root.right);// 递归遍历右子树
		} else {
			return;
		}
	}
	
	// 后序遍历 递归
	public static void postOrderWithRecursion(TreeNode root){
		if (root!=null){
			postOrderWithRecursion(root.left);// 递归遍历左子树
			postOrderWithRecursion(root.right);// 递归遍历右子树
			System.out.print(root.val);// 访问当前节点数据
		} else {
			return;
		}
	}
	
	// 层级遍历
	public static void levelOrder(TreeNode root){
		// 创建一个辅助队列，如果根不为空，加入队列
		Queue<TreeNode> queue = new LinkedList<>();
		if (root!=null){
			queue.add(root);
		} else {
			return;
		}
		
		// 队列不为空时
		while (!queue.isEmpty()){
			// 遍历树的每一层节点
			int len = queue.size();//获取每层的节点数
			for (int i=0; i<len; i++){//遍历每层节点
				// 获取 队列头元素，访问节点值，如果左右子树不为空，加入队列
				TreeNode node = queue.poll();
				System.out.print(node.val);
				if (node.left!=null)    queue.add(node.left);
				if (node.right!=null)   queue.add(node.right);
			}
		}
	}
	
	// 前序遍历 非递归
	public static void preOrderWithNonRecursion(TreeNode root){
		
	}
	// 中序遍历 非递归
	public static void inOrderWithNonRecursion(TreeNode root){
		
	}
	// 后序遍历 非递归
	public static void postOrderWithNonRecursion(TreeNode root){
		
	}
	
	public static void main(String[] args) {
//		TreeNode root = TreeNode.creatBinaryTree();
//		TreeNode.preOrderWithRecursion(root);
//		System.out.println();
//		TreeNode.inOrderWithRecursion(root);
//		System.out.println();
//		TreeNode.postOrderWithRecursion(root);
//		System.out.println();
//		TreeNode.levelOrder(root);
//		System.out.println();
		
		TreeNode root2 = TreeNode.createTest();
		List<List<Integer>> list = TreeNode.zigzagLevelOrder(root2);
		int len = list.size();
		for (int i=0; i<len; i++){
			System.out.println(list.get(i));
		}
	}
	
	public static TreeNode createTest(){
		int[] arr = {1,2,3,4,5};
		TreeNode root = new TreeNode(arr[0]);
		TreeNode child1 = new TreeNode(arr[1]);
		TreeNode child2 = new TreeNode(arr[2]);
		TreeNode child3 = new TreeNode(arr[3]);
		TreeNode child4 = new TreeNode(arr[4]);
		
		root.left = child1;
		root.right = child2;
		child1.left = child3;
		child2.right = child4;
		return root;
	}
	
	public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> list = new LinkedList<>();
		helper(root, list);
		return list;
	}
	
	public static void helper(TreeNode root, List<List<Integer>> list){
		//辅助双端队列，存放每层的节点
		Deque<TreeNode> deque = new LinkedList<>();
		if(root!=null){
			deque.addLast(root);
		} else {
			return;
		}
		
		// 遍历树的层，j 记录层数
		for(int j=0; !deque.isEmpty(); j++){
			//每层 定义一个临时 list,添加当前层的节点
			List<Integer> templist = new LinkedList<>();
			
			int len = deque.size();//获取当前层节点的数量
			for(int i = 0; i<len; i++){//遍历这一层的所有节点
				TreeNode node;
				if (j%2==0){//如果是偶数层，先取队尾元素，然后 先插左子树，再插右子树 到队头
					node = deque.pollLast();
					templist.add(node.val);
					if(node.left!=null)     deque.addFirst(node.left);
					if(node.right!=null)    deque.addFirst(node.right);
				} else {//如果是奇数层，先取队头元素，然后 先插右子树，再插 左子树到 队尾
					node = deque.pollFirst();
					templist.add(node.val);
					if(node.right!=null)    deque.addLast(node.right);
					if(node.left!=null)     deque.addLast(node.left);
				}
			}
			
			//将临时list 添加到 最终的list
			list.add(templist);
		}
		
	}
	
}
